λ¬Έμ
μ¬λ¬ μ¬μΌλ‘ μ΄λ£¨μ΄μ§ λλΌκ° μλ€. μ΄ λλΌμ λν΅λ Ήμ μ¬μ μλ λ€λ¦¬λ₯Ό λ§λ€κ² λ€λ 곡μ½μΌλ‘ μΈκΈ°λͺ°μ΄λ₯Ό ν΄ λΉμ λ μ μμλ€. νμ§λ§ λ§μ λν΅λ Ήμ μ·¨μνμ, λ€λ¦¬λ₯Ό λλλ€λ κ²μ΄ μκΉλ€λ μκ°μ νκ² λμλ€. κ·Έλμ κ·Έλ, μμλ΄λ μμΌλ‘ ν μ¬κ³Ό λ€λ₯Έ μ¬μ μλ λ€λ¦¬ νλλ§μ λ§λ€κΈ°λ‘ νμκ³ , κ·Έ λν λ€λ¦¬λ₯Ό κ°μ₯ μ§§κ² νμ¬ λμ μλΌλ € νμλ€.
μ΄ λλΌλ NΓNν¬κΈ°μ μ΄μ°¨μ νλ©΄μμ μ‘΄μ¬νλ€. μ΄ λλΌλ μ¬λ¬ μ¬μΌλ‘ μ΄λ£¨μ΄μ Έ μμΌλ©°, μ¬μ΄λ λμλ¨λΆμΌλ‘ μ‘μ§κ° λΆμ΄μλ λ©μ΄λ¦¬λ₯Ό λ§νλ€.
κ·Έλ¦Όμμ μμ΄ μλ λΆλΆμ΄ μ‘μ§μ΄κ³ , μμ΄ μλ λΆλΆμ΄ λ°λ€μ΄λ€. μ΄ λ°λ€μ κ°μ₯ μ§§μ λ€λ¦¬λ₯Ό λμ λ λλ₯μ μ°κ²°νκ³ μ νλ€. κ°μ₯ μ§§μ λ€λ¦¬λ, λ€λ¦¬κ° 격μμμ μ°¨μ§νλ μΉΈμ μκ° κ°μ₯ μμ λ€λ¦¬λ₯Ό λ§νλ€. λ€μ κ·Έλ¦Όμμ λ λλ₯μ μ°κ²°νλ λ€λ¦¬λ₯Ό λ³Ό μ μλ€.
λ¬Όλ‘ μμ λ°©λ² μΈμλ λ€λ¦¬λ₯Ό λλ λ°©λ²μ΄ μ¬λ¬ κ°μ§ μμΌλ, μμ κ²½μ°κ° λλ λ€λ¦¬μ κΈΈμ΄κ° 3μΌλ‘ κ°μ₯ μ§§λ€(λ¬Όλ‘ κΈΈμ΄κ° 3μΈ λ€λ₯Έ λ€λ¦¬λ₯Ό λμ μ μλ λ°©λ²λ λͺ κ°μ§ μλ€). μ§λκ° μ£Όμ΄μ§ λ, κ°μ₯ μ§§μ λ€λ¦¬ νλλ₯Ό λμ λ λλ₯μ μ°κ²°νλ λ°©λ²μ μ°ΎμΌμμ€.
μ λ ₯
- 첫 μ€μλ μ§λμ ν¬κΈ° N(100μ΄νμ μμ°μ)κ° μ£Όμ΄μ§λ€. κ·Έ λ€μ Nμ€μλ Nκ°μ μ«μκ° λΉμΉΈμ μ¬μ΄μ λκ³ μ£Όμ΄μ§λ©°, 0μ λ°λ€, 1μ μ‘μ§λ₯Ό λνλΈλ€. νμ λ κ° μ΄μμ μ¬μ΄ μλ λ°μ΄ν°λ§ μ λ ₯μΌλ‘ μ£Όμ΄μ§λ€.
μΆλ ₯
- 첫째 μ€μ κ°μ₯ μ§§μ λ€λ¦¬μ κΈΈμ΄λ₯Ό μΆλ ₯νλ€.
π Logic
class Loc {
int x;
int y;
int cnt;
public Loc(int x, int y, int cnt) {
this.x = x;
this.y = y;
this.cnt = cnt;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public int getCnt() {
return cnt;
}
}
- κ° μ μ λ³ μ’ν λ° νμ¬ μ μ κΉμ§ μ€λλ° νμν λ€λ¦¬ μλ₯Ό μ μ₯νκΈ° μν΄ μ¬μ©νλ ν΄λμ€
class Graph {
final int[][] graph;
boolean[][] discovered;
Queue<Loc> q = new LinkedList<>();
int[] w_way = { 1, 0, -1, 0 };
int[] y_way = { 0, 1, 0, -1 };
int bridge = Integer.MAX_VALUE;
int graph_size;
...
}
- κ·Έλνμ μ 보λ₯Ό μ μ₯νκΈ° μν΄ μ¬μ©νλ ν΄λμ€
private int buildBridge(int x, int y) {
discovered = new boolean[graph_size][graph_size];
q = new LinkedList<>();
q.add(new Loc(x, y, 0));
int cur_land = graph[x][y];
discovered[x][y] = true;
while(!q.isEmpty()) {
Loc loc = q.poll();
int cur_x = loc.getX();
int cur_y = loc.getY();
int cnt = loc.getCnt();
if (graph[cur_x][cur_y] != 0 && graph[cur_x][cur_y] != cur_land) return cnt;
for (int i = 0; i < 4; i++) {
int nextX = cur_x + w_way[i], nextY = cur_y + y_way[i];
if (nextX < 0 || nextX >= graph_size || nextY < 0 || nextY >= graph_size) continue;
if (discovered[nextX][nextY] || graph[nextX][nextY] == cur_land) continue;
discovered[nextX][nextY] = true;
q.add(new Loc(nextX, nextY, cnt+1));
}
}
return -1;
}
- ꡬλΆλ λλ₯ μ 보λ₯Ό κ°μ§κ³ , μλ‘ λ€λ₯Έ λλ₯μ μλ λ€λ¦¬λ₯Ό λμ보λ λ©μλ
if (graph[cur_x][cur_y] != 0 && graph[cur_x][cur_y] != cur_land) return cnt;μ ν΅ν΄ μλ‘ λ€λ₯Έ λλ₯μ μ΄μ κ²½μ° μ¬μ©λλ€λ¦¬ κΈΈμ΄ + 1μ΄ λ°ν- λ°©λ¬Ένμ§ μμ
0, μ¦ λ°λ€μ κ²½μ°μλ§ κ³μQueueμ μΆκ°
π CODE
μ½λ 보기/μ κΈ°π«
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
class Loc {
int x;
int y;
int cnt;
public Loc(int x, int y, int cnt) {
this.x = x;
this.y = y;
this.cnt = cnt;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public int getCnt() {
return cnt;
}
}
class Graph {
final int[][] graph;
boolean[][] discovered;
Queue<Loc> q = new LinkedList<>();
int[] w_way = { 1, 0, -1, 0 };
int[] y_way = { 0, 1, 0, -1 };
int bridge = Integer.MAX_VALUE;
int graph_size;
public Graph(int size) {
graph_size = size;
this.graph = new int[graph_size][graph_size];
discovered = new boolean[graph_size][graph_size];
}
public void AddElement(String line, int idx) {
String[] tmp = line.split(" ");
for(int i = 0; i < graph_size; i++) {
graph[idx][i] = Integer.parseInt(tmp[i]);
}
}
public void identifyLand() {
int land = 2;
for (int i = 0; i < graph_size; i++) {
for (int j = 0; j < graph_size; j++) {
if (!discovered[i][j] && graph[i][j] == 1) {
fillLand(i, j, land);
land++;
}
}
}
}
private void fillLand(int x, int y, int land) {
graph[x][y] = land;
discovered[x][y] = true;
q.add(new Loc(x, y, 0));
while(!q.isEmpty()) {
Loc loc = q.poll();
int nowX = loc.getX();
int nowY = loc.getY();
for (int i = 0; i < 4; i++) {
int nextX = nowX + w_way[i], nextY = nowY + y_way[i];
if (nextX < 0 || nextX >= graph_size || nextY < 0 || nextY >= graph_size) continue;
if (discovered[nextX][nextY]) continue;
if (graph[nextX][nextY] == 1) {
graph[nextX][nextY] = land;
discovered[nextX][nextY] = true;
q.add(new Loc(nextX, nextY, 0));
}
}
}
}
public void solution() {
for (int i = 0; i < graph_size; i++) {
for (int j = 0; j < graph_size; j++) {
if (graph[i][j] > 0) {
int cnt = buildBridge(i, j);
if (cnt == -1) continue;
bridge = Math.min(bridge, cnt);
}
}
}
System.out.println(bridge - 1);
}
private int buildBridge(int x, int y) {
discovered = new boolean[graph_size][graph_size];
q = new LinkedList<>();
q.add(new Loc(x, y, 0));
int cur_land = graph[x][y];
discovered[x][y] = true;
while(!q.isEmpty()) {
Loc loc = q.poll();
int cur_x = loc.getX();
int cur_y = loc.getY();
int cnt = loc.getCnt();
if (graph[cur_x][cur_y] != 0 && graph[cur_x][cur_y] != cur_land) return cnt;
for (int i = 0; i < 4; i++) {
int nextX = cur_x + w_way[i], nextY = cur_y + y_way[i];
if (nextX < 0 || nextX >= graph_size || nextY < 0 || nextY >= graph_size) continue;
if (discovered[nextX][nextY] || graph[nextX][nextY] == cur_land) continue;
discovered[nextX][nextY] = true;
q.add(new Loc(nextX, nextY, cnt+1));
}
}
return -1;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
Graph g = new Graph(N);
String line="";
for (int idx = 0; idx < N; idx++) {
line = br.readLine();
g.AddElement(line, idx);
}
g.identifyLand();
g.solution();
br.close();
}
}
βοΈ Review
Queueμ λ°μ΄ν° μΆκ°, μμ , κ²μ μ μ¬μ©νλ λ©μλλ€ μ€ μ μ¬ν κΈ°λ₯μ νλ λ©μλλ€μ μ°¨μ΄λ₯Ό μλ μ°Έκ³ λΈλ‘κ·Έμμ νμΈν μ μμλ€.-
μ¬μ ꡬλΆνμ¬ μ μ₯νκ³ , μ΄ν λ€λ¦¬λ₯Ό 건μ€ν λ μ¬μ κ°μ₯μ리λΆν° νμμ μμνλ©΄ μ΄λ¨κΉλΌλ μκ°μ νλ€.
- μ¬μ κ°μ₯μ리λ₯Ό ꡬλΆν΄ μ μ₯ν΄λκ³ νμνλ €λ, μ¬μ κ°μ₯μ리λ₯Ό ꡬλΆνλ κ²μ΄ λ¬Έμ μλ€.
- μ¬μ κ°μ₯μ리λ₯Ό ꡬλΆνμ§ μκ³ ,
λΈλ£¨νΈ ν¬μ€μ²λΌ λͺ¨λ μ¬μ μ’νμμ νμνλ λ°©μμΌλ‘ λ³κ²½νκ³ , λ©λͺ¨λ¦¬ μ΄κ³Όκ° λ°μνλ€.
graph[nowX][nowY] = land;
discovered[nowX][nowY] = true;
for (int i = 0; i < 4; i++) {
int nextX = nowX + w_way[i], nextY = nowY + y_way[i];
if (nextX >= 0 && nextX < graph_size && nextY >= 0 && nextY < graph_size && graph[nextX][nextY] == 1 && !discovered[nextX][nextY]) {
q.add(new Loc(nextX, nextY, 0));
}
}
// μ μ½λλ₯Ό μλμ κ°μ΄ λ³κ²½, λ©λͺ¨λ¦¬ μ΄κ³Όκ° λ°μνμ§ μμ
if (nextX < 0 || nextX >= graph_size || nextY < 0 || nextY >= graph_size) continue;
if (discovered[nextX][nextY]) continue;
if (graph[nextX][nextY] == 1) {
graph[nextX][nextY] = land;
discovered[nextX][nextY] = true;
q.add(new Loc(nextX, nextY, 0));
}
- λΈλ‘κ·Έλ₯Ό μ°Έκ³ νμ¬ μμ μ½λ μμ μΌλ‘ λ©λͺ¨λ¦¬μ΄κ³Όλ₯Ό νΌν μ μμλλ°, λ Όλ¦¬μ μΌλ‘ μ΄ν΄κ° κ°μ§ μλλ€...
π μΆμ²
https://www.acmicpc.net/problem/2146